Content-Addressable Memories (CAMs) use semi-conductor memory components such as Static Random Access Memory (SRAM) circuits and additional comparison circuitry that permits any required searches to be completed in a single clock cycle. Searches using Content-Addressable Memories and associated comparison circuitry are typically faster than algorithmic searches. Because Content-Addressable Memories are faster, they are often used in Internet routers for complicated address look-up functions. They are also used in database accelerators, data compression applications, neural networks, Translation Look-aside Buffers (TLB) and processor caches.
In a Content-Addressable Memory, any data is typically stored randomly in different memory locations, which are selected by an address bus. Data is also typically written directly into a first entry or memory location. Each memory location could have associated with the memory a pair of special status bits that keep track of whether the memory location includes valid data or is empty and available for overriding. Any information stored at a specific memory location is located by comparing every bit in memory with any data placed in a comparand register. A match flag is asserted to allow a user to know that the data is in memory. Priority encoders sort the matching locations by priority and make address-matching location available to a user.
As compared to more standard memory address circuits, in a Content-Addressable Memory circuit data is supplied and an address obtained, and thus, address lines are not required. A router address look-up search examines a destination address for incoming packets and the address look-up table to find an appropriate output port. This algorithm and circuitry involves longest-prefix matching and uses the Internet Protocol (IP) networking standard.
Current routing tables have about 30,000 entries or more and the number of entries is increasing growing rapidly. Terabit-class routers perform hundreds of millions of searches per second and update routing tables thousands of times per second. Because of present and future projected routing requirements, Content-Addressable Memories are used to complete a search in a single cycle. In these circuits, comparison circuitry is usually added to every CAM memory cell, forming a parallel look-up engine. The CAM memory cells can be arranged in horizontal words, such as four horizontal words that are each five bits long. The cells contain both storage and comparison circuitry. Search lines run vertically and broadcast search data to the CAM cells. Match lines run horizontally across the array and indicate whether a search data matches the word in the row. An activated match line indicates a match, and a deactivated match line indicates a non-match or mismatch. The match lines are input to the priority encoder which generates an address corresponding to a match location.
Typically, a search will begin by pre-charging high all match lines in a matched state. Data is broadcast by drivers onto search lines. The CAM cells compare the stored bit against a bit on corresponding search lines. Any cells that match data do not affect match lines, but any cells with a mismatch would pull-down a match line for any word that has at least one mismatch. Other match lines without mismatches remain precharged high.
The priority encoder will generate a search address location for any matching data. For example, an encoder could select numerically the smallest numbered match line for two activated match lines and generate a match address, for example 01. This can be input to a RAM that contains output ports. The match address output is a pointer that retrieves associated data from RAM. An SRAM cell could include positive feedback in a back-to-back inverter with two access transistors connecting bit lines to storage nodes under control of a word line. Data is written or read into and from a cell through the bit lines. Mismatches result in discharged match lines and power consumption is the result. There are more mismatches typically than matches.
The circuit can be arrayed to handle a number of binary divisible row locations. A column structure can be hierarchical in nature. In a CAM application, it is sometimes necessary to encode one or more row locations. Because only one location can typically be encoded at a time, the locations are prioritized and the highest priorities are encoded. The priority can be set based on a physical order. CAM devices typically require a physical prioritization. Usually a priority encoder is done with many stages of combinational logic. These priority encoders often use a circuit requiring a large footprint and often limits performance.
Copending, commonly assigned U.S. patent application Ser. No. 11/134,890 by the same inventor, the disclosure which is hereby incorporated by reference in its entirety, discloses an improved physical priority encoder that is advantageous over priority encoders that use many stages of combinational logic. Instead, this physical priority encoder uses precharged circuits that include precharged bus lines and physical priority ordering, based on a top down approach, resulting in a small footprint. In this disclosed physical priority encoder, precharged bus lines are used as dynamic circuits, which result in higher performance in a smaller footprint. When this physical priority encoder is operative with a Content-Addressable Memory (CAM), each row can produce a match signal indicating that compare data is matched to the row data. A 4-bit priority encoder can be built using a 2-bit encoder footprint. Additional arrayed blocks can be cascaded and precharged bus lines and operative to aid in converting bus priorities to usable binary addresses.
In this type of described system, a Content-Addressable Memory (CAM) device would include an array of CAM cells arranged in columns and rows. Each row would have a match signal indicative that compare data has matched data within the respective row. This physical priority encoder is operatively connected to this array of CAM cells and determines a highest priority matching address for data within the array of CAM cells. Match lines are associated with respective rows and precharged bus lines are connected into respective match lines that are discharged whenever there is a match signal, such that the highest precharged bus line that is discharged results in an encoded address.
The priority encoder includes a plurality of n-bit encoder circuits that are cascaded together to accommodate the number of address bits as necessary for the array of CAM cells. Carry signals on a most significant n-bit encoder circuit feed match lines on less significant cascaded n-bit encoder circuits. A logic circuit can be used for inhibiting a carry operation or allowing a carry operation to the next cascaded encoder circuit.
An n-bit encoder circuit can be formed as a 2-bit encoder circuit having four rows. Precharged bus lines can be charged high at the beginning of an encoding cycle. Each match line can be formed as a pull-down transistor that discharges a precharged bus line when a match signal on a match line is high. Each pull-down transistor can also be formed as a gate connected to a respective match line, a source connected to ground, and a drain connected to a respective precharged bus line. Match lines can also be ordered in priority of bit addresses with the most significant bit addresses followed by least significant bit addresses. A precharge circuit can also be operatively connected to the precharged bus lines for charging the precharged bus lines high at the beginning of an encoding cycle. Each precharge circuit can comprise a transistor that pulls each precharged bus line to VDD at the beginning of an encoding cycle.
Although this disclosed physical priority encoder uses a top down approach and saves physical space, the array of objects are still addressed in a physical order. It would be advantageous if the objects could have a physical position overwritten based on a programmed order. In some physical priority encoders, rows would have to be shuffled physically if the priority of that row changes. It would be more advantageous if a programmable approach were used for this type of described system.